package leetcode.editor.cn;

//给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
// 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：n = 11
//输出：0
//解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2³¹ - 1 
// 
// Related Topics 数学 二分查找 👍 299 👎 0

//Java：第 N 位数字
public class NthDigit_400{
    public static void main(String[] args) {
        Solution solution = new NthDigit_400().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findNthDigit(int n) {
        int rest=n, i=1;
        while(rest>9*Math.pow(10,i-1)*i){
            rest-=9*Math.pow(10,i-1)*i;
            i++;
        }
        int num = rest/i;
        rest%=i;
        if (rest>0){
            num = (int)(Math.pow(10,i-1))+num;
            System.out.println(num);
            return (int)(num/Math.pow(10,i-rest)%10);
        }else{
            num = (int)(Math.pow(10,i-1))+num-1;
            System.out.println(num);
            return num%10;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
